// 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

// 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。



int res_cnt, **res;
void pushback(int *elem, int** returnColumnSizes) {
    res[res_cnt] = malloc(sizeof(int)*2);
    res[res_cnt][0] = elem[0];
    res[res_cnt][1] = elem[1];
    (* returnColumnSizes)[res_cnt] = 2;
    res_cnt++;
}

int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes){

    res = malloc(sizeof(int *)*(intervalsSize+1));
    *returnColumnSizes = malloc(sizeof(int)*(intervalsSize+1));
    res_cnt = 0;

    int *insert = newInterval;
    for (int i = 0; i < intervalsSize; i++) {

        if (insert == NULL) {  // 区间已插入
            pushback(intervals[i], returnColumnSizes);
            continue;
        } else if ( intervals[i][1] < insert[0]) {  // 左边无相交
            pushback(intervals[i], returnColumnSizes);
        } else if (insert[1] < intervals[i][0]) {   // 右边无相交，[0,1]或[4,5] 插入[[2,3],[6,8]]
            pushback(insert, returnColumnSizes);
            insert = NULL;
            pushback(intervals[i], returnColumnSizes);
        } else {        // 相交，合并区间
            insert[0] = fmin(intervals[i][0], insert[0]);
            insert[1] = fmax(intervals[i][1], insert[1]);
            if ((i < intervalsSize-1) && insert[1] >= intervals[i+1][0])    //还能继续合并 
                ;
            else {
                pushback(insert, returnColumnSizes);
                insert = NULL;
            }
        }    
    }
    if (insert) {   // [10,11] 插入[[2,3],[6,8]]
        pushback(insert, returnColumnSizes);    
    }

    *returnSize = res_cnt;
    return res;
}




